#include <stdio.h>

#define N 7

void swap(int *arr, int left, int right)
{
    int t = arr[left];
    arr[left] = arr[right];
    arr[right] = t;
}

int partition(int *A, int left, int right)
{
    int i = left, j = right;
    while (i < j)
    {
        // find less than pivot
        while (j > i && A[j] >= A[left])
        {
            --j;
        }
        // find more than pivot
        while (i < j && A[i] <= A[left])
        {
            ++i;
        }
        // swap
        if (i < j)
        {
            swap(A, i, j);
        }
        }
    // swap pivot
    swap(A, left, i);
    // return basis
    return i;
}

void quick_sort(int *A, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int pivot = partition(A, left, right);
    // left
    quick_sort(A, left, pivot - 1);
    // right
    quick_sort(A, pivot + 1, right);
}
int main()
{
    int A[N] = {
        49,
        38,
        65,
        97,
        76,
        13,
        27,
    };
    quick_sort(A, 0, N - 1);
    for (int i = 0; i < N; i++)
    {
        printf("%d ", A[i]);
    }

    return 0;
}